#include <bitset>
#include "main/utils.h"
using namespace std;

int occurOnceInTwo(const vector<int> &vec) {
  int ret = 0;
  for (size_t i = 0; i < vec.size(); ++i) {
    ret ^= vec[i];
  }
  return ret;
}

int findBit1Idx(int num) {
  int last_idx = 1;
  while (!(num & last_idx) && last_idx < (1 << 31)) {
    last_idx = last_idx << 1;
  }
  return last_idx;
}

vector<int> twoNumOccurOnceInTwo(const vector<int> &vec) {
  int xor_num = occurOnceInTwo(vec);
  int bit1Idx = findBit1Idx(xor_num);
  vector<int> vec1, vec2;
  for (size_t i = 0; i < vec.size(); ++i) {
    if (vec[i] & bit1Idx) {
      vec1.push_back(vec[i]);
    } else {
      vec2.push_back(vec[i]);
    }
  }
  vector<int> ret_nums;
  ret_nums.push_back(occurOnceInTwo(vec1));
  ret_nums.push_back(occurOnceInTwo(vec2));
  return ret_nums;
}

int occurOnceInThree(const vector<int> &vec) {
  vector<int> tmp(32, 0);
  for (int i = 0; i < vec.size(); ++i) {
    for (int j = 0; j < 32; ++j) {
      if (vec[i] & (1 << j)) {
        ++tmp[j];
      }
    }
  }
  int ret = 0;
  for (int i = 0; i < 32; ++i) {
    if (tmp[i] % 3) {
      ret += (1 << i);
    }
  }
  return ret;
}

int main() {
  vector<int> vec = {2, 5, 8, 0, 3, 6, 8, 0, 2, 5, 3};
  int num = occurOnceInTwo(vec);
  cout << "The number occur once in array, others occur twice: " << num << endl;

  vec = {2, 5, 8, 0, 3, 6, 8, 0, 2, 5};
  vector<int> nums = twoNumOccurOnceInTwo(vec);
  cout << "Two number occur once in array, others occur twice: " << nums[0] << " " << nums[1] << endl;

  vec = {2, 7, 9, 3, 5, 9, 7, 2, 9, 5, 5, 2, 7};
  num = occurOnceInThree(vec);
  cout << "The numver occur once in array, others occur thrice: " << num << endl;

  return 0;
}
